package com.sheng.leetcode.year2023.month02.day22;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2023/02/22
 * <p>
 * 1140. 石子游戏 II<p>
 * <p>
 * 爱丽丝和鲍勃继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。<p>
 * 爱丽丝和鲍勃轮流进行，爱丽丝先开始。最初，M = 1。<p>
 * 在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。<p>
 * 游戏一直持续到所有石子都被拿走。<p>
 * 假设爱丽丝和鲍勃都发挥出最佳水平，返回爱丽丝可以得到的最大数量的石头。<p>
 * <p>
 * 示例 1：<p>
 * 输入：piles = [2,7,9,4,4]<p>
 * 输出：10<p>
 * 解释：如果一开始Alice取了一堆，Bob取了两堆，然后Alice再取两堆。爱丽丝可以得到2 + 4 + 4 = 10堆。<p>
 * 如果Alice一开始拿走了两堆，那么Bob可以拿走剩下的三堆。在这种情况下，Alice得到2 + 7 = 9堆。返回10，因为它更大。<p>
 * <p>
 * 示例 2:<p>
 * 输入：piles = [1,2,3,4,5,100]<p>
 * 输出：104<p>
 * <p>
 * 提示：<p>
 * 1 <= piles.length <= 100<p>
 * 1 <= piles[i] <= 10^4<p>
 * <p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/stone-game-ii">1140. 石子游戏 II</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class LeetCode1140 {

    @Test
    public void test01() {
        int[] piles = {2, 7, 9, 4, 4};
//        int[] piles = {1, 2, 3, 4, 5, 100};
        System.out.println(new Solution().stoneGameII(piles));
    }
}

/**
 * 由于玩家每次可以拿走前 X 堆的所有石子，也就是说能拿走一个连续区间的石子，因此，我们可以先预处理出一个长度为 n + 1 的前缀和数组 s，其中
 * s[i] 表示数组 piles 的前 i 个元素的和。
 * 然后我们设计一个函数 dfs(i, m)，表示当前轮到的人可以从数组 piles 的下标 i 开始拿，且当前的 M 为 m 时，
 * 当前轮到的人能够拿到的最大石子数。初始时爱丽丝从下标 0 开始，且 M = 1，所以答案为 dfs(0,1)。
 * 函数 dfs(i, m) 的计算过程如下：
 * 如果当前轮到的人可以拿走剩下的所有石子，即
 * m × 2 ≥ n − i，能够拿到的最大石子数为 s[n] − s[i]；
 * 否则，当前轮到的人可以拿走剩下的前 x 堆的所有石子，其中 1 ≤ x ≤ 2m，能够拿到的最大石子数为
 * s[n] − s[i] − dfs(i + x, max(m, x))。也即是说，当前轮的人能够拿到的石子数为当前剩下的所有石子数减去下一轮对手能够拿到的石子数。
 * 我们需要枚举所有的 x，取其中的最大值作为函数 dfs(i, m) 的返回值。
 * 为了避免重复计算，我们可以使用记忆化搜索。
 * 最后，我们返回将 dfs(0, 1) 作为答案返回即可。
 * <p>
 * 作者：lcbin
 * 链接：https://leetcode.cn/problems/stone-game-ii/solution/python3javacgo-yi-ti-yi-jie-qian-zhui-he-flo7/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 */
class Solution {

    int n;

    int[] s;

    Integer[][] f;

    public int stoneGameII(int[] piles) {
        // 每个回合中，玩家可以拿走剩下的前 X 堆的所有石子，其中 1 <= X <= 2M，然后令 M = Math.max(M, X)，返回能取到的最大的石子数量
        n = piles.length;
        s = new int[n + 1];
        f = new Integer[n][n + 1];
        // s[i] 表示数组 piles 的前 i 个元素的和
        for (int i = 0; i < n; i++) {
            s[i + 1] = s[i] + piles[i];
        }
        // m 的初始值为 1，从 0 开始取石子
        return dfs(0, 1);
    }

    public int dfs(int i, int m) {
        // 判断当前轮到的人是否可以拿走所有的石子
        if (m * 2 >= n - i) {
            return s[n] - s[i];
        }
        if (f[i][m] != null) {
            return f[i][m];
        }
        int ans = 0;
        // 枚举所有的 x，取其中的最大值作为返回值
        for (int x = 1; x <= m * 2; x++) {
            // 当前轮到的人可以拿走的石子数为当前剩下的所有石子数减去下一轮对手能够拿到的石子数
            ans = Math.max(ans, s[n] - s[i] - dfs(i + x, Math.max(m, x)));
        }
        // 使用记忆化搜索，避免重复计算
        return f[i][m] = ans;
    }
}
